package com.github.hgkmail.hello.leetcode101.pointer.graph.topologicalsort;

import java.util.*;

//判断有向图是否存在回路，使用拓扑排序（UnionFind只能判断无向图是否有环。。。）
public class LC207CourseSchedule {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //创建图和入度列表
        List<List<Integer>> graph = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        int[] inDegree = new int[numCourses];
        Arrays.fill(inDegree, 0);
        //初始化图和入度列表
        for (int[] req:prerequisites) {
            int startVertex=req[1];
            int endVertex=req[0];
            graph.get(startVertex).add(endVertex);
            inDegree[endVertex]++;
        }
        //bfs，入度为0的订点入队
        Queue<Integer> queue = new ArrayDeque<>(numCourses);
        List<Integer> sortRes=new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i]==0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int u=queue.poll();
            sortRes.add(u);
            for (int v:graph.get(u)) {
                inDegree[v]--;
                if (inDegree[v]==0) {
                    queue.offer(v);
                }
            }
        }
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i]>0) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {

    }
}
